package com.lans.binary;

/**
 * @author: lans
 * @date: 2025/3/1
 * @name: 刘宇
 */
public class IndexMinQueue <T extends Comparable<T>>{
    private T[] items;//存储元素的数组

    private int[] pq;//保存每个元素在items数组中的索引,pq是堆有序的

    private int[] qp;//记录pq的逆序,pq中的索引是qp中的元素 pq中的元素是qp索引

    private int N;

    public IndexMinQueue(int size){
        items = (T[])new Comparable[size];
        pq  = new int[size+1];
        qp  = new int[size+1];
        N=0;
        for(int i=0;i<qp.length;i++){
            qp[i]=-1;
        }
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }

    public boolean less(int i, int j){
        //通过pq找到items中对应的元素
        return items[pq[i]].compareTo(items[pq[j]])<0;
    }

    public void exch(int i, int j){
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;

        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    public boolean contains(int k){
        return qp[k]!=-1;
    }

    //获取最小索引
    public int minIndex(){
        return pq[1];
    }

    public void insert(int i,T t){
        if(contains(i)){
            throw new RuntimeException("该索引已存在");
        }
        N++;
        items[i]=t;
        pq[N]=i;
        qp[i]=N;
        //上浮
        swim(N);
    }

    //删除
    public int delMin(){
        int minIndex = pq[1];
        //与N位置进行交换
        exch(1,N);
        //删除qp中索引对应的pq[N]
        qp[pq[N]]=-1;
        //删除pq中索引N的值
        items[minIndex]=null;
        N--;
        sink(1);
        return minIndex;
    }

    public void delete(int i){
        //找出在pq位置的索引
        int k = pq[i];
        exch(k,N);
        //删除qp中的索引值
        qp[pq[N]]=-1;
        //删除pq对应的索引值
        pq[N]=-1;
        //删除item对应元素
        items[i]=null;
        N--;
        sink(k);
        swim(k);
    }

    public void sink(int k){
        while(2*k<=N){
            int min = 2*k;
            if(2*k+1<=N&&less(2*k+1,2*k)){
                min = 2*k+1;
            }
            if(less(k,min)){
                break;
            }
            exch(k,min);
            k=min;
        }
    }

    public void swim(int k){
        while(k>1){
            if(less(k,k/2)){
                exch(k,k/2);
            }
            k=k/2;
        }
    }

    public static void main(String[] args) {
        String[] strings = {"S","C","W","E","A","B","N","A"};
        IndexMinQueue<String> queue = new IndexMinQueue<>(15);
        for(int i=0;i<strings.length;i++){
            queue.insert(i,strings[i]);
        }
        System.out.println(queue.size());
        //获取最小值的索引
        System.out.println(queue.minIndex());
        int minIndex=-1;
        while(!queue.isEmpty()){
            minIndex = queue.delMin();
            System.out.print(minIndex+",");
        }
    }
}